# -*- coding: utf-8 -*-

"""剑指 Offer II 057. 值和下标之差都在给定的范围内
给你一个整数数组 nums 和两个整数 k 和 t 。请你判断是否存在 两个不同下标 i 和 j，使得 abs(nums[i] - nums[j]) <= t ，同时又满足 abs(i - j) <= k 。
如果存在则返回 true，不存在返回 false。

示例 1：
输入：nums = [1,2,3,1], k = 3, t = 0
输出：true

示例 2：
输入：nums = [1,0,1,1], k = 1, t = 2
输出：true

示例 3：
输入：nums = [1,5,9,1,5,9], k = 2, t = 3
输出：false

提示：
0 <= nums.length <= 2 * 10^4
-2^31 <= nums[i] <= 2^31 - 1
0 <= k <= 10^4
0 <= t <= 2^31 - 1"""


from bisect import bisect_right

class Solution:
    """开始没有思路，当画了一个数组之后就有了。
    维护一个长度为 k 的窗口，对窗口内的元素进行排序（python内置快排），移动窗口，用二分查找查询，或者插入。
    窗口移动，只需要在删除头前节点，判断待添加进来的尾后节点在有序数组中的位置前后差值就可以了。
    
    题解中用到有序集合，可以用跳表或者红黑树实现快速查找，快速插入删除操作，但是这两种数据结构因为要维持平衡性，都有一定难度，还没有掌握"""
    def containsNearbyAlmostDuplicate(self, nums, k: int, t: int) -> bool:
        window = nums[0:k+1]
        window.sort()
        for i in range(len(window)-1):
            if window[i+1] - window[i] <= t:
                return True

        window.insert(0, float('-inf'))
        window.append(float('inf'))
        
        iscontains = False
        head, tail = 0, k
        while True:
            try:
                window.pop(bisect_right(window, nums[head])-1)

                wi = bisect_right(window, nums[tail+1])
                appended = nums[tail+1]
                if appended-window[wi-1] <= t or window[wi]-appended <= t:
                    iscontains = True
                    break
                window.insert(wi, appended)
                head += 1
                tail += 1
            except IndexError:
                break
        return iscontains


if __name__ == '__main__':
    so = Solution()
    print(so.containsNearbyAlmostDuplicate(nums = [1,2,3,1], k = 3, t = 0))
    print(so.containsNearbyAlmostDuplicate(nums = [1,0,1,1], k = 1, t = 2))
    print(so.containsNearbyAlmostDuplicate(nums = [1,5,9,1,5,9], k = 2, t = 3))
    print(so.containsNearbyAlmostDuplicate(nums = [1,2,1,1], k = 1, t = 0))
